package cn.zhl.tree;

import cn.zhl.tree.binarysearch.BinarySearchTree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-05-03 14:14
 **/
public class BinaryTree<E> implements Tree<E> {

	public Visitor<E> visitor;
	protected int size;
	protected Node root;

	public BinaryTree() {
	}

	public Node getRoot() {
		return root;
	}

	@Override
	public void beforeIterate(Visitor<E> visitor) {
//        ArrayList<E> rs = new ArrayList<>();
//        before1(visitor,root);
//        before2(rs,root);
//        before3(visitor,root);
		levelEach(visitor);
	}

	/**
	 * 递归方式:前序遍历  父左右
	 *
	 * @param visitor
	 * @param node
	 */
	private void before1(Visitor visitor, Node node) {
		if (node == null || visitor.stop) {
			return;
		}
		visitor.stop = visitor.visit(node.element);
		before1(visitor, node.left);
		before1(visitor, node.right);
	}

	/**
	 * 递归方式:中序遍历  左父右  或者   右父左
	 *
	 * @param visitor
	 * @param node
	 */
	private void before2(Visitor visitor, Node node) {
		if (node == null || visitor.stop) {
			return;
		}
		before2(visitor, node.left);
		if (visitor.stop) {
			return;
		}
		visitor.stop = visitor.visit(node.element);
		before2(visitor, node.right);
	}

	/**
	 * 递归方式:后序遍历  左右父
	 *
	 * @param visitor
	 * @param node
	 */
	private void before3(Visitor visitor, Node node) {
		if (node == null || visitor.stop) {
			return;
		}
		before3(visitor, node.left);
		before3(visitor, node.right);
		if (visitor.stop) {
			return;
		}
		visitor.stop = visitor.visit(node.element);
	}

	/**
	 * 递归方式:层序遍历  一层一层的遍历，
	 */
	private void levelEach(Visitor<E> visitor) {
		Queue<Node> queue = new LinkedList<>();
		if (root == null) {
			return;
		}
		queue.offer(root);
		while (!queue.isEmpty()) {
			Node poll = queue.poll();
			if (poll != null) {
				queue.offer(poll.left);
				queue.offer(poll.right);
				visitor.visit(poll.element);
			}
		}
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void clear() {
		root = null;
		size = 0;
	}


	protected void elementNotNullCheck(E e) {
		if (null == e) {
			throw new IllegalArgumentException("element must not be null!");
		}
	}

	@Override
	public boolean isComplete() {
		if (root == null) {
			return false;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);
		boolean leaf = false;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			if (leaf && !node.isLeaf()) {
				return false;
			}
			if (node.left != null) {
				queue.offer(node.left);
			} else if (node.right != null) {
				//左空右不空 返回false
				return false;
			}
			if (node.right != null) {
				queue.offer(node.right);
			} else {
				leaf = true;
			}
		}
		return true;
	}

	/**
	 * 递归方式求高度
	 *
	 * @return
	 */
	@Override
	public int height() {
//        return height(root);
		return heightIter1();
	}

	private int height(Node node) {
		if (node == null) {
			return 0;
		}
		return 1 + Math.max(height(node.left), height(node.right));
	}

	/**
	 * 非递归方式求高度
	 */
	public int heightIter1() {
		Queue<Node> queue = new LinkedList<>();
		if (root == null) {
			return 0;
		}
		queue.offer(root);
		int height = 0;
		int times = 1;
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			times--;
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
			if (times == 0) {
				height++;
				times = queue.size();
			}
		}
		return height;
	}

	/**
	 * 非递归方式求高度
	 */
	public int heightIter2() {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);
		Node node = null;
		while (!queue.isEmpty()) {
			node = queue.poll();
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
		}
		int i = 0;
		while (node != null) {
			i++;
			node = node.parent;
		}
		return i;
	}

	public Node predecessor(Node node) {
		if (node == null) {
			return null;
		}
		Node p = node.left;
		if (p != null) {
			while (p.right != null) {
				p = p.right;
			}
			return p;
		}
		//來到这里就说明left == null
		while (node.parent != null && node.parent.left == node) {
			node = node.parent;
		}
		return node.parent;
	}

	@Override
	public Tree reverse() {
		if (root == null) {
			return null;
		}
		Node newNode = new Node(root.element, null);
		fz(root, newNode);
		BinarySearchTree<E> newTree = new BinarySearchTree<>();
		newTree.root = newNode;
		return newTree;
	}

	private void fz(Node oldNode, Node newNode) {
		Node oldLeft = oldNode.left;
		Node newLeft = null;
		if (oldLeft != null) {
			newLeft = new Node(oldLeft.element, newNode);
			fz(oldLeft, newLeft);
		}
		Node oldRight = oldNode.right;
		Node newRight = null;
		if (oldRight != null) {
			newRight = new Node(oldRight.element, newNode);
			fz(oldRight, newRight);
		}
	}

	protected Node createNode(E e,Node parent){
		return new Node(e,parent);
	}

	protected class Node {
		public E element;
		public Node left;
		public Node right;
		public Node parent;

		public Node(E element, Node parent) {
			this.element = element;
			this.parent = parent;
		}

		public boolean isLeaf() {
			return left == null && right == null;
		}

		public boolean hasTwoChildren(){
			return left != null && right != null;
		}

		public boolean isLeftChild(){
			return parent != null && this == parent.left;
		}
		public boolean isRightChild(){
			return parent != null && this == parent.right;
		}

		public Node sibling(){
			if(isLeftChild()){
				return parent.right;
			}
			if(isRightChild()){
				return parent.left;
			}
			return null;
		}
		public Node uncle(){
			if(parent == null){
				return null;
			}
			return parent.sibling();
		}

		@Override
		public String toString() {
			return element.toString();
		}
	}
}
